package backtracking;

/**
 * 79.单词搜索
 * 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
 * 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
 */

/**
 * hot100一刷
 */
public class exist {

    int[][] dir = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    boolean flag = false;
    boolean[][] visited;

    public boolean exist(char[][] board, String word) {
        visited = new boolean[board.length][board[0].length];

        // 遍历整个二维数组，尝试以每个元素为起点
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                // 找到首字符后，开始dfs
                if (board[i][j] == word.charAt(0)) {
                    visited[i][j] = true;
                    dfs(board, word, i, j, 1);
                    visited[i][j] = false;
                    // 一旦发现匹配，就返回true不再继续
                    if (flag) return true;
                }
            }
        }
        return false;
    }

    /**
     * @param start 表示已经匹配到了 word 的第 start 个字符
     */
    public void dfs(char[][] board, String word, int i, int j, int start) {
        // 递归结束条件：当 start == word.length() 时，说明已经完全匹配
        if (start == word.length()) {
            flag = true;
            return;
        }
        // 如果已经找到答案，可立即返回（避免不必要的递归）
        if (flag) return;

        // 从上下左右四个方向搜索
        for (int[] d : dir) {
            int newX = i + d[0], newY = j + d[1];
            // 越界、已访问、或不同字符直接跳过
            if (newX < 0 || newX >= board.length || newY < 0 || newY >= board[0].length
                    || visited[newX][newY] || board[newX][newY] != word.charAt(start)) {
                continue;
            }
            // 递归搜索
            visited[newX][newY] = true;
            dfs(board, word, newX, newY, start + 1);
            visited[newX][newY] = false;
            // 已经找到目标可立即停止
            if (flag) return;
        }
    }

}

/**
 * hot100二刷
 */
class exist2 {
    int[][] dir = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    boolean flag = false;

    public boolean exist(char[][] board, String word) {
        boolean[][] visited = new boolean[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (board[i][j] == word.charAt(0)) {
                    visited[i][j] = true;
                    dfs(board, word, 1, visited, i, j);
                    if (flag) return true;
                    visited[i][j] = false;
                }
            }
        }
        return false;
    }

    public void dfs(char[][] board, String word, int start, boolean[][] visited, int x, int y) {
        if (start == word.length()) {
            flag = true;
            return;
        }
        for (int i = 0; i < 4; i++) {
            int newX = x + dir[i][0], newY = y + dir[i][1];
            if (newX < 0 || newX >= board.length || newY < 0 || newY >= board[0].length) continue;
            if (!visited[newX][newY] && board[newX][newY] == word.charAt(start)) {
                visited[newX][newY] = true;
                dfs(board, word, start + 1, visited, newX, newY);
                visited[newX][newY] = false;
            }
        }
    }
}


